package com.zhj.bz.datastructure.linkedlist;

import com.zhj.algorithm.sort.HeapSort;

import java.util.Stack;

/**
 * @author zhj
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(1);
        singleLinkedList.addByOrder(3);
        singleLinkedList.addByOrder(2);
        singleLinkedList.addByOrder(6);
        singleLinkedList.addByOrder(4);
        singleLinkedList.delete(4);
        singleLinkedList.show();
        System.out.println(singleLinkedList.getLen());
        System.out.println(singleLinkedList.findLastIndexValue(1));
        singleLinkedList.reverse();
        singleLinkedList.show();
        singleLinkedList.reverseShow();
    }
}
class SingleLinkedList {
    private Node head = new Node(0);

    /**
     * 尾插
     * @param value
     */
    public void add(int value) {
        Node temp = head;
        while (null != temp.getNext()) {
            temp = temp.getNext();
        }
        Node node = new Node(value);
        temp.setNext(node);
    }

    /**
     * 根据值的顺序添加
     * @param value
     */
    public void addByOrder(int value) {
        Node temp = head;
        boolean flag = false;
        while (null != temp.getNext()) {
            if (value == temp.getNext().getValue()) {
                flag = true;
                break;
            }
            if (value < temp.getNext().getValue()) {
                break;
            }
            temp = temp.getNext();
        }
        if (flag) {
            System.out.println("该值已存在，请勿重复插入");
        } else {
            Node node = new Node(value);
            if (null != temp.getNext()) {
                node.setNext(temp.getNext());
            }
            temp.setNext(node);
        }
    }

    /**
     * 根据下标修改
     * @param index
     * @param value
     */
    public void update(int index, int value) {
        Node temp = head;
        int cur_index = 0;
        boolean flag = false;
        while (null != temp.getNext()) {
            if (index == cur_index) {
                flag = true;
                break;
            }
            cur_index++;
            temp = temp.getNext();
        }
        Node node = new Node(value);
        if (flag) {
            if (null != temp.getNext()) {
                node.setNext(temp.getNext());
            }
            temp.setNext(node);
        } else {
            System.out.println("下标越界！");
        }
    }

    /**
     * 根据下标删除
     * @param index
     */
    public void delete(int index) {
        Node temp = head;
        int cur_index = 0;
        boolean flag = false;
        while (null != temp.getNext()) {
            if (index == cur_index) {
                flag = true;
                break;
            }
            cur_index++;
            temp = temp.getNext();
        }
        if (flag) {
            if (null != temp.getNext()) {
                if (null != temp.getNext().getNext()) {
                    temp.setNext(temp.getNext().getNext());
                } else {
                    temp.setNext(null);
                }
            }
        } else {
            System.out.println("下标越界！");
        }
    }

    /**
     * 数据展示
     */
    public void show() {
        if (null == head.getNext()) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head;
        while (null != temp.getNext()) {
            temp = temp.getNext();
            System.out.print(temp.getValue() + "\t");
        }
        System.out.println();
    }

    /**
     * 获取长度
     * @return
     */
    public int getLen() {
        int index = 0;
        if (null == head.getNext()) {
            return index;
        }
        Node temp = head;
        while (null != temp.getNext()) {
            temp = temp.getNext();
            index++;
        }
        return index;
    }

    /**
     * 查找倒数节点
     * @param index
     * @return
     */
    public int findLastIndexValue(int index) {
        int value = 0;
        if (null == head.getNext()) {
            throw new RuntimeException("队列为空");
        }
        if (getLen() - index < 0) {
            throw new RuntimeException("下标超过最大长度");
        }
        index = getLen() - index + 1;
        int cur_index = 0;
        Node temp = head;
        while (null != temp.getNext()) {
            if (cur_index == index) {
                break;
            }
            temp = temp.getNext();
            cur_index++;
        }
        return temp.getValue();
    }

    /**
     * 翻转(头插)
     */
    public void reverse() {
        if (null == head.getNext() || null == head.getNext().getNext()) {
            return;
        }
        Node cur = head.getNext();
        Node next = null;
        head = new Node(0);
        while (null != cur) {
            next = cur.getNext();
            cur.setNext(head.getNext());
            head.setNext(cur);
            cur = next;
        }
    }

    /**
     * 逆序打印
     * 思路一：先翻转再打印（性能贼差）
     * 思路二：放入栈中再打印
     */
    public void reverseShow() {
        if (head.getNext() == null) {
            return;
        }
        Stack stack = new Stack();
        Node temp = head;
        while (null != temp.getNext()) {
            temp = temp.getNext();
            stack.push(temp.getValue());
        }
        while (stack.size() > 0) {
            System.out.print(stack.pop() + "\t");
        }
        System.out.println();
    }
}
class Node {
    private int value;
    private Node next;

    public Node(int value){
        this.value = value;
        this.next = null;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
